package org.example.algorithm.array;

//线段树解法
public class MaxSubArraySolution2 {
    public class SegmentInfo {
        public int lSum;
        public int rSum;
        public int sum;
        public int maxSum;

        public SegmentInfo(int lSum, int rSum, int sum, int maxSum) {
            this.lSum = lSum;
            this.rSum = rSum;
            this.sum = sum;
            this.maxSum = maxSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return getSegmentInfo(nums, 0, nums.length-1).maxSum;
    }

    public SegmentInfo getSegmentInfo(int[] nums, int from, int to) {
        if (from == to) {
            return new SegmentInfo(nums[from], nums[from], nums[from], nums[from]);
        }
        int middle = (from + to) >> 1;
        return mergeSegementInfo(getSegmentInfo(nums, from, middle), getSegmentInfo(nums, middle+1, to));
    }

    private SegmentInfo mergeSegementInfo(SegmentInfo segmentInfo1, SegmentInfo segmentInfo2) {
        int sum = segmentInfo1.sum + segmentInfo2.sum;
        int lSum = Math.max(segmentInfo1.lSum, segmentInfo1.sum + segmentInfo2.lSum);
        int rSum = Math.max(segmentInfo2.rSum, segmentInfo1.rSum + segmentInfo2.sum);
        int maxSum = Math.max(Math.max(segmentInfo1.maxSum, segmentInfo2.maxSum), segmentInfo1.rSum+segmentInfo2.lSum);
        return new SegmentInfo(lSum, rSum, sum, maxSum);
    }

}
